package com.lw.leetcode.back.c;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * back
 * 2290. 到达角落需要移除障碍物的最小数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/30 11:30
 */
public class MinimumObstacles {


    public static void main(String[] args) {
        MinimumObstacles test = new MinimumObstacles();

        // 2
        int[][] arr = {{0, 1, 1}, {1, 1, 0}, {1, 1, 0}};

        int i = test.minimumObstacles(arr);

        for (int[] ints : test.arr) {
            System.out.println(Arrays.toString(ints));
        }

        System.out.println(i);
    }

    private int m;
    private int n;
    private int[] flag;
    private int[][] arr;
    private LinkedList<Long> list = new LinkedList<>();
    private int[][] grid;

    public int minimumObstacles(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        flag = new int[m * n];
        arr = new int[m][n];
        this.grid = grid;
        arr[0][0] = grid[0][0];
        list.add(0L);
        flag[0] = 1;
        while (!list.isEmpty()) {
            long poll = list.poll();
            int x = (int) (poll >> 32);
            int y = (int) poll;
            if (y > 0 && find(x, y - 1, arr[x][y ] )) {
                return arr[m - 1][n - 1];
            }
            if (y < n - 1 && find(x, y + 1, arr[x][y ] )) {
                return arr[m - 1][n - 1];
            }
            if (x > 0 && find(x - 1, y, arr[x][y] )) {
                return arr[m - 1][n - 1];
            }
            if (x < m - 1 && find(x + 1, y, arr[x][y] )) {
                return arr[m - 1][n - 1];
            }
        }
        return arr[m - 1][n - 1];
    }

    private boolean find(int x, int y, int count) {
        if (x == m - 1 && y == n - 1) {
            arr[x][y] = count;
            return true;
        }
        if (x < 0 || x == m || y < 0 || y == n) {
            return false;
        }
        if (flag[x * n + y] == 1) {
            return false;
        }
        flag[x * n + y] = 1;
        if (grid[x][y] == 0) {
            arr[x][y] = count;
            return find(x - 1, y, count) ||
                    find(x + 1, y, count) ||
                    find(x, y + 1, count) ||
                    find(x, y - 1, count);
        } else {
            arr[x][y] = count + 1;
            list.add(((long) x << 32) + y);
            return false;
        }
    }

}
